package com.ai.zuochengyun.phase01.class08;

public class Code02_CardsInLine {

    /**
     * 这是一个零和游戏，先手获得的多，那么后手就获得少，所以先手是取max，后手是取min
     * @param args
     */
    public static void main(String[] args) {
        int[] arr = {50, 100, 20, 10};
        // 先手肯定先拿10，然后作为后手打算要拿到最大值，那么你肯定先拿到10，然后对手拿50，但是此时你又拿到了100
        // 所以正好对应f先手函数
//        int[] arr = {1, 100, 1};

        System.out.println(win1(arr));
        System.out.println(win2(arr));
        System.out.println(win3(arr));
    }

    /**
     * 获胜者的分数
     * 不一定先手必胜，比如[1, 100, 1]
     *
     * f 和 g整体上在l l+1.。。。r范围内做决定
     * f 和 g整体上在l .。。。r-1 r范围内做决定
     *
     * @param arr
     * @return
     */
    public static int win1(int[] arr) {
        if (arr == null || arr.length < 1) {
            return 0;
        }
        // 作为先手
        int first = f1(arr, 0, arr.length - 1);
        // 作为后手
        int second = g1(arr, 0, arr.length - 1);
        // 两者取较大的值
        return Math.max(first, second);
    }

    /**
     * 作为先手，肯定会保证当前这轮和接下来的一轮之和能获取到最大的
     *
     * @param arr
     * @param l
     * @param r
     * @return
     */
    public static int f1(int[] arr, int l, int r) {
        // 只有一张牌，你是先手，那么牌面的值就是你能获取的值
        if (l == r) {
            return arr[l];
        }
        // 当前在fdp表的（l,r）位置
        // 取左边的值 + 作为后手在（l+1,r）范围内能取到的值
        int p1 = arr[l] + g1(arr, l + 1, r);
        // 取右边的值 + 作为后手在（l,r-1）范围内能取到的值
        int p2 = arr[r] + g1(arr, l, r - 1);
        // 作为先手，有优先选择的权力，所以肯定取较大值
        return Math.max(p1, p2);
    }

    /**
     * 作为后手，此刻会作为先手在[l + 1, r] 或者 [l, r - 1]的范围去取，但是先手肯定会给你留较小的值
     *
     * @param arr
     * @param l
     * @param r
     * @return
     */
    public static int g1(int[] arr, int l, int r) {
        // 只有一张牌，你是后手，那么你就获取不到牌，所以值为0
        if (l == r) {
            return 0;
        }
        // 当前在gdp表的（l,r）位置，需要依赖fdg中（l+1, r）和（l, r-1）位置的值

        // 后手尽力去找最优
        int p1 = f1(arr, l + 1, r);
        int p2 = f1(arr, l, r - 1);

        // 你作为后手，先手肯定会让后手挑一个较小最优的值
        return Math.min(p1, p2);
    }


    /**
     * 获胜者的分数
     * 不一定先手必胜，比如[1, 100, 1]
     *
     * @param arr
     * @return
     */
    public static int win2(int[] arr) {
        if (arr == null || arr.length < 1) {
            return 0;
        }

        int n = arr.length;
        int[][] fdp = new int[n][n];
        int[][] gdp = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                fdp[i][j] = -1;
                gdp[i][j] = -1;
            }
        }

        int first = f2(arr, 0, arr.length - 1, fdp, gdp);
        int second = g2(arr, 0, arr.length - 1, fdp, gdp);
        return Math.max(first, second);
    }

    /**
     * 作为先手
     *
     * @param arr
     * @param l
     * @param r
     * @return
     */
    public static int f2(int[] arr, int l, int r, int[][] fdp, int[][] gdp) {
        if (fdp[l][r] != -1) {
            return fdp[l][r];
        }

        int ans = 0;
        if (l == r) {
            ans = arr[l];
        } else {
            int p1 = arr[l] + g2(arr, l + 1, r, fdp, gdp);
            int p2 = arr[r] + g2(arr, l, r - 1, fdp, gdp);
            ans = Math.max(p1, p2);
        }
        fdp[l][r] = ans;
        return ans;
    }

    /**
     * 作为后手
     *
     * @param arr
     * @param l
     * @param r
     * @return
     */
    public static int g2(int[] arr, int l, int r, int[][] fdp, int[][] gdp) {
        if (gdp[l][r] != -1) {
            return gdp[l][r];
        }
        int ans = 0;
        if (l != r) {
            int p1 = f2(arr, l + 1, r, fdp, gdp);
            int p2 = f2(arr, l, r - 1, fdp, gdp);
            ans = Math.min(p1, p2);
        }
        gdp[l][r] = ans;
        return ans;
    }

    /**
     * 获胜者的分数
     * 不一定先手必胜，比如[1, 100, 1]
     *
     * @param arr
     * @return
     */
    public static int win3(int[] arr) {
        if (arr == null || arr.length < 1) {
            return 0;
        }

        int n = arr.length;
        int[][] fdp = new int[n][n];
        int[][] gdp = new int[n][n];

        // 按照对角线的方向初始化fdp
        for (int i = 0; i < n; i++) {
            fdp[i][i] = arr[i];
        }

        // 初始化其他格子数据
        // 外层列
        for (int startCol = 1; startCol < n; startCol++) {
            int l = 0;
            int r = startCol;

            // l是从0开始的所以不会超出n，但是r有可能会超过n，所以只要判断r小于n，就跳出循环
            while (r < n) {
                gdp[l][r] = Math.min(fdp[l + 1][r], fdp[l][r - 1]);
                fdp[l][r] = Math.max(arr[l] + gdp[l + 1][r], arr[r] + gdp[l][r - 1]);
                l++;
                r++;
            }
        }
        return Math.max(fdp[0][n - 1], gdp[0][n - 1]);
    }
}
